package acm.pta14;

import 左哥算法.compare.comparator.MyComparator;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

public class 浪漫侧影2 {
    static Tree root;
    static List<Integer> left = new LinkedList<>();
    static List<Integer> right = new LinkedList<>();
    static Map<Integer, Integer> indexMap = new HashMap<>();

    public static void main(String[] args) {
        Random r = new Random();
        new MyComparator(container -> {
            int n = r.nextInt(10) + 1;
            container.addEnd(n);
            Set<Integer> set = new LinkedHashSet<>();
            while (set.size() < n) {
                set.add(r.nextInt(20));
            }
            container.addAllEnd(set);
            List<Integer> list = set.stream().sorted((o1, o2) -> r.nextInt()).collect(Collectors.toList());
            container.addAll(list);
        }).compare(浪漫侧影::main, 浪漫侧影2::fun);
    }


    public static void fun(String[] args) {
        Reader sc = new Reader();
        left.clear();
        right.clear();
        indexMap.clear();
        int n = sc.nextInt();
        int[] inOrder = new int[n];
        int[] postOrder = new int[n];
        for (int i = 0; i < n; i++) {
            inOrder[i] = sc.nextInt();
            indexMap.put(inOrder[i], i);
        }
        for (int i = 0; i < n; i++) {
            postOrder[i] = sc.nextInt();
        }
        root = build(inOrder, postOrder, 0, 0, n);
        levelOrder();
        System.out.print("R:");
        right.forEach(i -> System.out.print(" " + i));
        System.out.println();
        System.out.print("L:");
        left.forEach(i -> System.out.print(" " + i));
        System.out.println();
    }

    /**
     * 层序遍历
     */
    public static void levelOrder() {
        Queue<Tree> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            LinkedList<Tree> list = new LinkedList<>();
            for (int i = 0; i < size; i++) {    //遍历当前层
                Tree cur = queue.poll();
                list.add(cur);
                if (cur.left != null) {
                    queue.add(cur.left);
                }
                if (cur.right != null) {
                    queue.add(cur.right);
                }
            }
            left.add(list.getFirst().val);
            right.add(list.getLast().val);
        }
    }

    public static Tree build(int[] inOrder, int[] postOrder, int is, int ps, int len) {
        if (len < 1) {
            return null;
        }
        if (len == 1) {
            return new Tree(inOrder[is]);
        }
        Tree cur = new Tree(postOrder[ps + len - 1]);
        int rootIndex = indexMap.get(cur.val);
        cur.left = build(inOrder, postOrder, is, ps, rootIndex - is);
        cur.right = build(inOrder, postOrder, rootIndex + 1, ps + (rootIndex - is), len - (rootIndex - is) - 1);
        return cur;
    }

    static class Tree {
        int val;
        Tree left;
        Tree right;

        public Tree(int val) {
            this.val = val;
        }
    }

    static class Reader {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");

        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException ex) {
                return null;
            }
        }

        public boolean hasNext() {
            while (!tokenizer.hasMoreTokens()) {    //内存中没有
                String nextLine = innerNextLine();
                if (nextLine == null) {     //且没有下一行
                    return false;
                }
                tokenizer = new StringTokenizer(nextLine);  //读入一行
            }
            return true;
        }

        public String nextLine() {
            tokenizer = new StringTokenizer("");    //清空内存中的字符
            return innerNextLine();
        }

        public void clear() {
            tokenizer = new StringTokenizer("");
        }

        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
//    public BigInteger nextBigInt() {
//        return new BigInteger(next());
//    }
    }

}
